Numerical integration of ordinary differential equations on manifolds

Summary This paper is concerned with the problem of developing numerical integration algorithms for differential equations that, when viewed as equations in some Euclidean space, naturally evolve on some embedded submanifold. It is desired to construct algorithms whose iterates also evolve on the same manifold. These algorithms can therefore be viewed as integrating ordinary differential equations on manifolds. The basic method “decouples” the computation of flows on the submanifold from the numerical integration process. It is shown that two classes of single-step and multistep algorithms can be posed and analyzed theoretically, using the concept of “freezing” the coefficients of differential operators obtained from the defining vector field. Explicit third-order algorithms are derived, with additional equations augmenting those of their classical counterparts, obtained from “obstructions” defined by nonvanishing Lie brackets.     

Local and Parallel Finite Element Algorithms for Eigenvalue Problems

Abstract Some new local and parallel finite element algorithms are proposed and analyzed in this paper foreigenvalue problems.With these algorithms, the solution of an eigenvalue problem on a fine grid is reduced tothe solution of an eigenvalue problem on a relatively coarse grid together with solutions of some linear algebraicsystems on fine grid by using some local and parallel procedure.A theoretical tool for analyzing these algorithmsis some local error estimate that is also obtained in this paper for finite element approximations of eigenvectorson general shape-regular grids.     

Generalization of Murty's direct algorithm to linear and convex quadratic programming

Murty's algorithm for the linear complementarity problem is generalized to solve the optimality conditions for linear and convex quadratic programming problems with both equality and inequality constraints. An implementation is suggested which provides both efficiency and tight error control. Numerical experiments as well as field tests in various applications show favorable results.The author thanks K. G. Murty for his encouragement and helpful comments.     

Affine-scaling for linear programs with free variables

The affine-scaling modification of Karmarkar's algorithm is extended to solve problems with free variables. This extended primal algorithm is used to prove two important results. First the geometrically elegant feasibility algorithm proposed by Chandru and Kochar is the same algorithm as the one obtained by appending a single column of residuals to the constraint matrix. Second the dual algorithm as first described by Adler et al., is the same as the extended primal algorithm applied to the dual.     

A new family of proximity graphs: Class cover catch digraphs

Motivated by issues in machine learning and statistical pattern classification, we investigate a class cover problem (CCP) with an associated family of directed graphs—class cover catch digraphs (CCCDs). CCCDs are a special case of catch digraphs. Solving the underlying CCP is equivalent to finding a smallest cardinality dominating set for the associated CCCD, which in turn provides regularization for statistical pattern classification. Some relevant properties of CCCDs are studied and a characterization of a family of CCCDs is given.     

Kalman filtering of a space-time Markov random field

In this paper, finite-dimensional recursive filters for space-time Markov random fields are derived. These filters can be used with the expectation maximization (EM) algorithm to yield maximum likelihood estimates of the parameters of the model.     

Numerical solutions of the shallow water equations with discontinuous bed topography

A simple scheme is developed for treatment of vertical bed topography in shallow water flows. The effect of the vertical step on flows is modelled with the shallow water equations including local energy loss terms. The bed elevation is denoted with z_b^‐ for the left and z_b⁺ for the right values at each grid point, hence exactly representing a discontinuity in the bed topography. The surface gradient method (SGM) is generalized to reconstruct water depths at cell interfaces involving a vertical step so that the fluxes at the cell interfaces can accurately be calculated with a Riemann solver. The scheme is verified by predicting a surge crossing a step, a tidal flow over a step and dam‐break flows on wet/dry beds. The results have shown good agreements compared with analytical solutions and available experimental data. The scheme is efficient, robust, and may be used for practical flow calculations. Copyright © 2002 John Wiley & Sons, Ltd.     

A stochastic algorithm using one sample point per iteration and diminishing stepsizes

A stochastic algorithm for finding stationary points of real-valued functions defined on a Euclidean space is analyzed. It is based on the Robbins-Monro stochastic approximation procedure. Gradient evaluations are done by means of Monte Carlo simulations. At each iteratex _i , one sample point is drawn from an underlying probability space, based on which the gradient is approximated. The descent direction is against the approximation of the gradient, and the stepsize is 1/i. It is shown that, under broad conditions, w.p.1 if the sequence of iteratesx ₁,x ₂,...generated by the algorithm is bounded, then all of its accumulation points are stationary.     

双色激光场中1维共线氢分子离子的经典动力学研究

 运用经典理论方法，并采用辛算法数值求解了双色激光场作用下1维共线氢分子离子(H₂⁺)的哈密顿正则方程，得到了氢分子离子在激光场下的经典轨迹。计算了单色场和双色场下氢分子离子(H₂⁺)的存活几率、电离几率、解离几率、库仑爆炸几率随时间的演化，分析了双色场的相位、强度、强度比及倍频的变化对氢分子离子动力学行为的影响,并给出了相应的物理解释。     

线性分式规划最优解集的求法

本文使用多面集的表示定理，导出了线性分式规划最优解集的结构，并给出确定全部最优解的计算步骤。